//GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG
// structures2.h		header file
//
// Author:			Cheng-en Guo
//
// Created Time:	07-24-99
// Revised Time:
//
// Descriptions:	This file is to define some common structures
//
// Member variables:
//
// Functions:
//
//GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG

#ifndef _CG_EDGELINKING_H_
#define _CG_EDGELINKING_H_

#include <math.h>
#include <memory.h>
#include <stdio.h>

#include "Matrix.h"

#define MIN_CNT_STRENGTH -1E10
#define MAX_CNT_STRENGTH 1E10
#define MAX_NEIGHBOR_NUM 10

#ifndef PI
#define PI 3.1415926535897931
#endif

#ifndef NULL
#define NULL 0
#endif

#ifndef BOOL
#define BOOL int
#endif

#ifndef BYTE
#define BYTE unsigned char
#endif

#ifndef TRUE
#define TRUE 1
#endif

#ifndef FALSE
#define FALSE 0
#endif


//class CContourNeighbor;
struct __GPOSITION { };
typedef __GPOSITION* GPOSITION;

enum ContourType { EPOINT, ELINE, EARC, ECURVE };

class CContour;

class CGPoint
{
public:
	int x, y;
	CGPoint() { x = 0; y = 0; }
//	CGPoint( CGPoint p ) { x = p.x; y = p.y; }
	CGPoint( int x0, int y0 ) { x = x0; y = y0; }
	CGPoint operator + ( CGPoint p )
	{
		CGPoint p2;
		p2.x = x + p.x;
		p2.y = y + p.y;
		return p2;
	}
	bool operator == ( CGPoint p )
	{
		if( x != p.x )
			return false;
		if( y != p.y )
			return false;
		return true;
	}
	bool operator != ( CGPoint p )
	{
		if( x == p.x && y == p.y )
			return false;
		return true;
	}
};

class CContourNeighbor
{
public:
	float m_fContinuityStrength;
	int m_nEnd;// flag of the strength is to the head of m_pContour or the tail of m_pContour, 0-head,1-tail,2-inside
	CContour * m_pContour;
	CGPoint m_Point;
	CContourNeighbor()
	{
		m_fContinuityStrength = MIN_CNT_STRENGTH;
		m_nEnd = 0;// flag of the strength is to the head of m_pContour or the tail of m_pContour, 0-head
		m_pContour = NULL;
	}
	CContourNeighbor( CContourNeighbor& cn )
	{
		m_fContinuityStrength = cn.m_fContinuityStrength;
		m_nEnd = cn.m_nEnd;// flag of the strength is to the head of m_pContour or the tail of m_pContour, 0-head
		m_pContour = cn.m_pContour;
		m_Point = cn.m_Point;
	}
/*	CContourNeighbor& operator = ( CContourNeighbor& cn )
	{
		m_fContinuityStrength = cn.m_fContinuityStrength;
		m_nEnd = cn.m_nEnd;// flag of the strength is to the head of m_pContour or the tail of m_pContour, 0-head
		m_pContour = cn.m_pContour;
		return *this;
	}*/
};

class CGPointList
{
	// attributes
protected:
	class CNode
	{
	public:
		CGPoint m_data;
		CNode *m_pNext;
		CNode *m_pPrev;
		CNode(){ m_pNext = NULL; m_pPrev = NULL; }
	};

protected:
public:
	CNode* m_pNodeHead;
	CNode* m_pNodeTail;
	int m_nSize;

	// operations
public:
	CGPointList()
	{
		m_pNodeHead = NULL;
		m_pNodeTail = NULL;
		m_nSize = 0;
	}
	~CGPointList()
	{
		RemoveAll();
	}
	void RemoveAll()
	{
		CNode *pNode = m_pNodeHead;
		while ( pNode != NULL )
		{
			CNode *pHead = pNode->m_pNext;
			delete pNode;
			pNode = pHead;
		}
		m_pNodeHead = NULL;
		m_pNodeTail = NULL;
		m_nSize = 0;
	}
	void AddHead( CGPoint p )
	{
		if( m_pNodeHead == NULL && m_pNodeTail == NULL )
		{
			CNode *pNode = new CNode;
			m_pNodeHead = pNode;
			m_pNodeTail = pNode;
			pNode->m_pNext = NULL;
			pNode->m_pPrev = NULL;
			pNode->m_data = p;
		}
		else
		{
			CNode *pOldHead = m_pNodeHead;
			CNode *pNode = new CNode;
			m_pNodeHead = pNode;
			pOldHead->m_pPrev = m_pNodeHead;
			m_pNodeHead->m_pNext = pOldHead;
			m_pNodeHead->m_pPrev = NULL;
			m_pNodeHead->m_data = p;
		}
		m_nSize++;
	}
	void AddTail( CGPoint p )
	{
		if( m_pNodeHead == NULL && m_pNodeTail == NULL )
		{
			CNode *pNode = new CNode;
			m_pNodeHead = pNode;
			m_pNodeTail = pNode;
			pNode->m_pNext = NULL;
			pNode->m_pPrev = NULL;
			pNode->m_data = p;

		}
		else
		{
			CNode *pOldTail = m_pNodeTail;
			CNode *pNode = new CNode;
			m_pNodeTail = pNode;
			pOldTail->m_pNext = m_pNodeTail;
			m_pNodeTail->m_pPrev = pOldTail;
			m_pNodeTail->m_pNext = NULL;
			m_pNodeTail->m_data = p;
		}
		m_nSize++;
	}
	void Add( int nEnd, CGPoint p )
	{
		if( nEnd == 0 )
			AddHead( p );
		else if( nEnd == 1 )
			AddTail( p );
	}
	inline int GetCount()
	{
		return m_nSize;
	}
	inline bool IsEmpty()
	{
		return ( m_nSize == 0 );
	}
	CGPoint& GetHead()
	{
		return m_pNodeHead->m_data;
	}
	CGPoint GetHead() const
	{
		return m_pNodeHead->m_data;
	}
	CGPoint& GetTail()
	{
		return m_pNodeTail->m_data;
	}
	CGPoint GetTail() const
	{
		return m_pNodeTail->m_data;
	}
	CGPoint GetHeadOrTail( int end ) const
	{
		if( end == 0 )
			return GetHead();
		else
			return GetTail();
	}
	GPOSITION GetHeadPosition() const
	{
		return (GPOSITION)m_pNodeHead;
	}
	GPOSITION GetTailPosition() const
	{
		return (GPOSITION)m_pNodeTail;
	}
	CGPoint GetNext(GPOSITION& rPosition)// return *Position++
	{
		CNode* pNode = (CNode*) rPosition;
		if (pNode==NULL)
		{
			CGPoint aa;		//a bug found by ztu
			return aa;
		}

		//ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
		rPosition = (GPOSITION) pNode->m_pNext;
		return pNode->m_data;
	}
	CGPoint GetNext(GPOSITION& rPosition) const // return *Position++
	{
		CNode* pNode = (CNode*) rPosition;
		//ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
		rPosition = (GPOSITION) pNode->m_pNext;
		return pNode->m_data;
	}
	CGPoint& GetPrev(GPOSITION& rPosition) // return *Position--
	{
		CNode* pNode = (CNode*) rPosition;
		//ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
		rPosition = (GPOSITION) pNode->m_pPrev;
		return pNode->m_data;
	}
	CGPoint GetPrev(GPOSITION& rPosition) const // return *Position--
	{
		CNode* pNode = (CNode*) rPosition;
		//ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
		rPosition = (GPOSITION) pNode->m_pPrev;
		return pNode->m_data;
	}
	CGPoint RemoveHead()
	{
		CGPoint p(0,0);
		if( m_pNodeHead == NULL && m_pNodeTail == NULL )
			return p;
		else
		{
			p = m_pNodeHead->m_data;
			CNode *pOldHead = m_pNodeHead;
			m_pNodeHead = pOldHead->m_pNext;
			delete pOldHead;
			if( m_pNodeHead == NULL )
				m_pNodeTail = NULL;
			else
				m_pNodeHead->m_pPrev = NULL;
			m_nSize--;
			return p;
		}
	}
	CGPoint RemoveTail()
	{
		CGPoint p(0,0);
		if( m_pNodeHead == NULL && m_pNodeTail == NULL )
			return p;
		else
		{
			p = m_pNodeTail->m_data;
			CNode *pOldTail = m_pNodeTail;
			m_pNodeTail = pOldTail->m_pPrev;
			delete pOldTail;
			if( m_pNodeTail == NULL )
				m_pNodeHead = NULL;
			else
				m_pNodeTail->m_pNext = NULL;
			m_nSize--;
			return p;
		}
	}
};

class CContour
{
public:
	CContour *m_pNext;
	CContour *m_pPrev;// CContour is a double linked list
	CGPointList	m_PointList;// the list of the points in this contour
	CContourNeighbor m_HeadPtNbrArray[MAX_NEIGHBOR_NUM];// The array which is save its neighbor to the head point
	CContourNeighbor m_TailPtNbrArray[MAX_NEIGHBOR_NUM];// The array which is save its neighbor to the head tail
	int m_nHeadNbrNum;
	int m_nTailNbrNum;
	ContourType	m_ContourType;//contour type: point, line, arc, curve
	BOOL		m_bClosed;// whether this contour is closed
	BOOL		m_bSplit;// whether this contour is closed and head is corner point
	int			m_nTheEndReachBoundary;//Which end reaches boundary, 0-head, 1-tail, 2-both, -1 none
	int			m_nTheEndMeetOtherContour;//Which end meets other contour, 0-head, 1-tail, 2-both, -1 none
	float		m_fAngleHead;// the angle of the head point
	float		m_fAngleTail;// the angle of the tail point
	float		m_fPara1;// parameter one, if this contour is arc, para1 means radium
	float		m_fPara2;// reserved
	int			m_nLastMoveDirection;// the direction of last move, 0,1,2...8
	float		m_fStrength;// average edge strength of this contour
	int			m_nLevel;// the level of the paramid 0 -- LEVEL_NUM-1
	BOOL		m_bExtendHeadTail[2];//whether need to extend head(0), whether need to extend tail(1)
	int			m_nHeadAndTailProperty[2];//[0]head,[1]tail, =-1 free,=0 reach itself, =1 reach other contour, =2 reach bounary
	CContour()
	{
		m_pNext = NULL;
		m_pPrev = NULL;
		m_PointList.RemoveAll();// the list of the points in this contour
		m_nHeadNbrNum = 0;
		m_nTailNbrNum = 0;
		m_ContourType =  EPOINT;//contour type: point, line, arc, curve
		m_bClosed = FALSE;// whether this contour is closed
		m_bSplit = FALSE;// whether this contour is closed and head is corner point
		m_nTheEndReachBoundary = -1;
		m_nTheEndMeetOtherContour = -1;
		m_fAngleHead = 0;// the angle of the head point
		m_fAngleTail = 0;// the angle of the tail point
		m_fPara1 = 0;// parameter one, if this contour is arc, para1 means radium
		m_fPara2 = 0;// reserved
		m_nLastMoveDirection = 0;// the direction of last move, 0,1,2...8
		m_bExtendHeadTail[0] = true;
		m_bExtendHeadTail[1] = true;
		m_fStrength = MIN_CNT_STRENGTH;
		m_nLevel = 0;
		m_nHeadAndTailProperty[0] = -1;//[0]head,[1]tail, =-1 free,=0 reach itself, =1 reach other contour, =2 reach bounary
		m_nHeadAndTailProperty[1] = -1;
	}
	CContour( CGPoint p1, CGPoint p2 )
	{
		m_pNext = NULL;
		m_pPrev = NULL;
		m_PointList.RemoveAll();// the list of the points in this contour
		m_nHeadNbrNum = 0;
		m_nTailNbrNum = 0;
		int dX = abs(p2.x - p1.x) + 1;
		int dY = abs(p2.y - p1.y) + 1;
		if( dX >= dY )
		{// x as variable
			int nStep = Sign( p2.x - p1.x );
			CGPoint p;
			if( nStep > 0 )
			{
				for( int i = p1.x+1; i <= p2.x-1; i += nStep )
				{
					p.x = i;
					p.y = (int)( p1.y + (float)(i-p1.x) / (p2.x-p1.x) * (p2.y-p1.y) );
					m_PointList.AddTail( p );
				}
			}
			else if( nStep < 0 )
			{
				for( int i = p1.x-1; i >= p2.x+1; i += nStep )
				{
					p.x = i;
					p.y = (int)( p1.y + (float)(i-p1.x) / (p2.x-p1.x) * (p2.y-p1.y) );
					m_PointList.AddTail( p );
				}
			}
		}
		else
		{// x as variable
			int nStep = Sign( p2.y - p1.y );
			CGPoint p;
			if( nStep > 0 )
			{
				for( int i = p1.y+1; i <= p2.y-1; i += nStep )
				{
					p.y = i;
					p.x = (int)( p1.x + (float)(i-p1.y) / (p2.y-p1.y) * (p2.x-p1.x) );
					m_PointList.AddTail( p );
				}
			}
			else if( nStep < 0 )
			{
				for( int i = p1.y-1; i >= p2.y+1; i += nStep )
				{
					p.y = i;
					p.x = (int)( p1.x + (float)(i-p1.y) / (p2.y-p1.y) * (p2.x-p1.x) );
					m_PointList.AddTail( p );
				}
			}
		}
		m_ContourType =  ELINE;//contour type: point, line, arc, curve
		m_bClosed = FALSE;// whether this contour is closed
		m_bSplit = FALSE;// whether this contour is closed and head is corner point
		m_nTheEndReachBoundary = -1;
		m_nTheEndMeetOtherContour = -1;
		m_fAngleHead = (float)((atan2( (float)(p2.x-p1.x), (float)(p2.y-p1.y) ))*180/PI);// the angle of the head point
		if( m_fAngleHead < 0 )
			m_fAngleHead += 180;
		m_fAngleTail = m_fAngleHead-180;// the angle of the tail point
		m_fPara1 = 0;// parameter one, if this contour is arc, para1 means radium
		m_fPara2 = 0;// reserved
		m_nLastMoveDirection = 0;// the direction of last move, 0,1,2...8
		m_bExtendHeadTail[0] = true;//still need to be extended
		m_bExtendHeadTail[1] = true;//still need to be extended
		m_fStrength = MIN_CNT_STRENGTH;
		m_nLevel = -1;
		m_nHeadAndTailProperty[0] = 1;
		m_nHeadAndTailProperty[1] = 1;
	}
	CContour & operator = ( CContour & c )
	{
		m_pNext = c.m_pNext;
		m_pPrev = c.m_pPrev;// CContour is a double linked list
		GPOSITION pos = c.m_PointList.GetHeadPosition();
		while ( pos != NULL )
		{
			CGPoint p = m_PointList.GetNext( pos );
			m_PointList.AddTail( p );// the list of the points in this contour
		}
		m_nHeadNbrNum = c.m_nHeadNbrNum;
		m_nTailNbrNum = c.m_nTailNbrNum;
		memcpy( m_HeadPtNbrArray, c.m_HeadPtNbrArray, m_nHeadNbrNum*sizeof(CContourNeighbor) );// The array which is save its neighbor to the head point
		memcpy( m_TailPtNbrArray, c.m_TailPtNbrArray, m_nTailNbrNum*sizeof(CContourNeighbor) );// The array which is save its neighbor to the head point
		m_ContourType =  c.m_ContourType;//contour type: point, line, arc, curve
		m_bClosed = c.m_bClosed;// whether this contour is closed
		m_bSplit = c.m_bSplit;// whether this contour is closed and head is corner point
		m_nTheEndReachBoundary = c.m_nTheEndReachBoundary;// whether this contour is part of image boundary
		m_nTheEndMeetOtherContour = c.m_nTheEndMeetOtherContour;
		m_fAngleHead = c.m_fAngleHead;// the angle of the head point
		m_fAngleTail = c.m_fAngleTail;// the angle of the tail point
		m_fPara1 = c.m_fPara1;// parameter one, if this contour is arc, para1 means radium
		m_fPara2 = c.m_fPara2;// reserved
		m_fStrength = c.m_fStrength;
		m_nLastMoveDirection = c.m_nLastMoveDirection;
		m_bExtendHeadTail[0] = c.m_bExtendHeadTail[0];
		m_bExtendHeadTail[1] = c.m_bExtendHeadTail[1];
		m_nLevel = c.m_nLevel;
		m_nHeadAndTailProperty[0] = c.m_nHeadAndTailProperty[0];
		m_nHeadAndTailProperty[1] = c.m_nHeadAndTailProperty[1];
		return *this;
	}
	void AddNeighbor( int end, CContourNeighbor ConNeighbor )
	{
		if( end == 0 )
		{
			if( m_nHeadNbrNum < MAX_NEIGHBOR_NUM )
			{
				m_HeadPtNbrArray[m_nHeadNbrNum] = ConNeighbor;
				m_nHeadNbrNum++;
			}
		}
		else
		{
			if( m_nTailNbrNum < MAX_NEIGHBOR_NUM )
			{
				m_TailPtNbrArray[m_nTailNbrNum] = ConNeighbor;
				m_nTailNbrNum++;
			}
		}
	}
	void ClearNeighbor( int end )
	{
		if( end == 0 )
			m_nHeadNbrNum = 0;
		else
			m_nTailNbrNum = 0;
	}
	CGPoint GetEndPoint( int end )
	{
		if( end == 0 )
			return m_PointList.GetHead();
		else
			return m_PointList.GetTail();
	}
	int GetNeighborNum( int end )
	{
		int nNeighborNum;
		if( end == 0 )
			nNeighborNum = m_nHeadNbrNum;
		else
			nNeighborNum = m_nTailNbrNum;
		return nNeighborNum;
	}
	CContourNeighbor GetNeighbor( int end, int i )
	{
		int nNeighborNum;
		if( end == 0 )
			nNeighborNum = m_nHeadNbrNum;
		else
			nNeighborNum = m_nTailNbrNum;
		if( i >= nNeighborNum )
		{
//			::MessageBox( NULL, "Get Neighbor Error!", "Error", MB_OK );
		}
		if( end == 0 )
			return m_HeadPtNbrArray[i];
		else
			return m_TailPtNbrArray[i];
	}
	int SortNeighbors( int end )
	{
		int nNeighborNum;
		CContourNeighbor *pNbrArray;
		if( end == 0 )
		{
			nNeighborNum = m_nHeadNbrNum;
			pNbrArray = m_HeadPtNbrArray;
		}
		else
		{
			nNeighborNum = m_nTailNbrNum;
			pNbrArray = m_TailPtNbrArray;
		}
		if( nNeighborNum <= 0 )
			return nNeighborNum;
		double dSumStrength = 0;
		int i;
		for( i = 0; i < nNeighborNum; i++ )
			dSumStrength += pNbrArray[i].m_fContinuityStrength;
		if( dSumStrength != 0 )
		{
			for( i = 0; i < nNeighborNum; i++ )
			{
//				if( dSumStrength < 0 )
//					pNbrArray[i].m_fContinuityStrength = -(float)(pNbrArray[i].m_fContinuityStrength / dSumStrength);
//				else
					pNbrArray[i].m_fContinuityStrength = (float)(pNbrArray[i].m_fContinuityStrength / dSumStrength);
			}
		}
		float fStrength = pNbrArray[0].m_fContinuityStrength;
		for( i = 0; i < nNeighborNum - 1; i++ )
		{
			for( int j = i + 1; j < nNeighborNum; j++ )
			{
				if( pNbrArray[i].m_fContinuityStrength < pNbrArray[j].m_fContinuityStrength )
				{
					CContourNeighbor temp;
					temp = pNbrArray[i];
					pNbrArray[i] = pNbrArray[j];
					pNbrArray[j] = temp;
				}
			}
		}
		return nNeighborNum;
	}
	void RemoveAllNeighbors()
	{
		m_nHeadNbrNum = 0;
		m_nTailNbrNum = 0;
	}
	BOOL NeighborJudge( int &end, CContourNeighbor &cn )
	{
		int nNeighborNum;
		CContourNeighbor *pNbrArray;
		nNeighborNum = m_nHeadNbrNum;
		pNbrArray = m_HeadPtNbrArray;
		int i;
		for( i = 0; i < nNeighborNum; i++ )
		{
			if( pNbrArray[i].m_pContour == cn.m_pContour )
			{
				end = 0;
				cn.m_nEnd = pNbrArray[i].m_nEnd;
				return TRUE;
			}
		}
		nNeighborNum = m_nTailNbrNum;
		pNbrArray = m_TailPtNbrArray;
		for( i = 0; i < nNeighborNum; i++ )
		{
			if( pNbrArray[i].m_pContour == cn.m_pContour )
			{
				end = 0;
				cn.m_nEnd = pNbrArray[i].m_nEnd;
				return TRUE;
			}
		}
		return FALSE;
	}//BOOL NeighborJudge( int &end, CContourNeighbor &cn )
	int GetLengthFromInsidePoint2OneEnd( int end, CGPoint p )
	{
		int nLength = 0;
		CGPoint pCur;
		if( end == 0 )
		{
			GPOSITION pos = m_PointList.GetHeadPosition();
			while( pos != NULL )
			{
				pCur = m_PointList.GetNext( pos );
				nLength++;
				if( pCur == p )
					break;
			}
		}
		else
		{
			GPOSITION pos = m_PointList.GetTailPosition();
			while( pos != NULL )
			{
				pCur = m_PointList.GetPrev( pos );
				nLength++;
				if( pCur == p )
					break;
			}
		}
		return nLength;
	}//int GetLengthFromInsidePoint2OneEnd( int end, CGPoint p )
	int Sign( int n )
	{
		if( n > 0 )
			return 1;
		else if( n < 0 )
			return -1;
		else
			return 0;
	}
};

class CPointerList
{
	// attributes
protected:
	class CNode
	{
	public:
		void* m_data;
		CNode *m_pNext;
		CNode *m_pPrev;
		CNode(){ m_pNext = NULL; m_pPrev = NULL; }
		~CNode() { m_data = NULL; m_pNext = NULL; m_pPrev = NULL; }
	};

protected:
	CNode* m_pNodeHead;
	CNode* m_pNodeTail;
	int m_nSize;

	// operations
public:
	CPointerList()
	{
		m_pNodeHead = NULL;
		m_pNodeTail = NULL;
		m_nSize = 0;
	}
	~CPointerList()
	{
		RemoveAll();
	}
	void RemoveAll()
	{
		CNode *pNode = m_pNodeHead;
		while ( pNode != NULL )
		{
			CNode *pHead = pNode->m_pNext;
			delete pNode;
			pNode = pHead;
		}
		m_pNodeHead = NULL;
		m_pNodeTail = NULL;
		m_nSize = 0;
	}
	void AddHead( void* p )
	{
		if( m_pNodeHead == NULL && m_pNodeTail == NULL )
		{
			CNode *pNode = new CNode;
			m_pNodeHead = pNode;
			m_pNodeTail = pNode;
			pNode->m_pNext = NULL;
			pNode->m_pPrev = NULL;
			pNode->m_data = p;
		}
		else
		{
			CNode *pOldHead = m_pNodeHead;
			CNode *pNode = new CNode;
			m_pNodeHead = pNode;
			pOldHead->m_pPrev = m_pNodeHead;
			m_pNodeHead->m_pNext = pOldHead;
			m_pNodeHead->m_pPrev = NULL;
			m_pNodeHead->m_data = p;
		}
		m_nSize++;
	}
	void AddTail( void* p )
	{
		if( m_pNodeHead == NULL && m_pNodeTail == NULL )
		{
			CNode *pNode = new CNode;
			m_pNodeHead = pNode;
			m_pNodeTail = pNode;
			pNode->m_pNext = NULL;
			pNode->m_pPrev = NULL;
			pNode->m_data = p;

		}
		else
		{
			CNode *pOldTail = m_pNodeTail;
			CNode *pNode = new CNode;
			m_pNodeTail = pNode;
			pOldTail->m_pNext = m_pNodeTail;
			m_pNodeTail->m_pPrev = pOldTail;
			m_pNodeTail->m_pNext = NULL;
			m_pNodeTail->m_data = p;
		}
		m_nSize++;
	}
	void Add( int nEnd, void* p )
	{
		if( nEnd == 0 )
			AddHead( p );
		else if( nEnd == 1 )
			AddTail( p );
	}
	inline int GetCount()
	{
		return m_nSize;
	}
	inline bool IsEmpty()
	{
		return ( m_nSize == 0 );
	}
	void* & GetHead()
	{
		return m_pNodeHead->m_data;
	}
	void* GetHead() const
	{
		return m_pNodeHead->m_data;
	}
	void* & GetTail()
	{
		return m_pNodeTail->m_data;
	}
	void* GetTail() const
	{
		return m_pNodeTail->m_data;
	}
	GPOSITION GetHeadPosition() const
	{
		return (GPOSITION)m_pNodeHead;
	}
	GPOSITION GetTailPosition() const
	{
		return (GPOSITION)m_pNodeTail;
	}
	void* & GetNext(GPOSITION& rPosition)// return *Position++
	{
		CNode* pNode = (CNode*) rPosition;
		//ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
		rPosition = (GPOSITION) pNode->m_pNext;
		return pNode->m_data;
	}
	void* GetNext(GPOSITION& rPosition) const // return *Position++
	{
		CNode* pNode = (CNode*) rPosition;
		//ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
		rPosition = (GPOSITION) pNode->m_pNext;
		return pNode->m_data;
	}
	void* & GetPrev(GPOSITION& rPosition) // return *Position--
	{
		CNode* pNode = (CNode*) rPosition;
		//ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
		rPosition = (GPOSITION) pNode->m_pPrev;
		return pNode->m_data;
	}
	void* GetPrev(GPOSITION& rPosition) const // return *Position--
	{
		CNode* pNode = (CNode*) rPosition;
		//ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
		rPosition = (GPOSITION) pNode->m_pPrev;
		return pNode->m_data;
	}
	void* RemoveHead()
	{
		void* p;
		if( m_pNodeHead == NULL && m_pNodeTail == NULL )
			return NULL;
		else
		{
			p = m_pNodeHead->m_data;
			CNode *pOldHead = m_pNodeHead;
			m_pNodeHead = pOldHead->m_pNext;
			if( m_pNodeHead == NULL )
				m_pNodeTail = NULL;
			delete pOldHead;
			m_pNodeHead->m_pPrev = NULL;
			m_nSize--;
			return p;
		}
	}
	void* RemoveTail()
	{
		void* p = NULL;
		if( m_pNodeHead == NULL && m_pNodeTail == NULL )
			return p;
		else
		{
			p = m_pNodeTail->m_data;
			CNode *pOldTail = m_pNodeTail;
			m_pNodeTail = pOldTail->m_pPrev;
			delete pOldTail;
			if( m_pNodeTail == NULL )
				m_pNodeHead = NULL;
			else
				m_pNodeTail->m_pNext = NULL;
			m_nSize--;
			return p;
		}
	}
};

class CContourList
{
	// attributes
public:
	CContour *m_pContourHead;
	CContour *m_pContourTail;
	int m_nSize;
	// operations
public:
	CContourList()
	{
		m_pContourHead = NULL;
		m_pContourTail = NULL;
		m_nSize = 0;
	}
	~CContourList()
	{
		RemoveAll();
	}
	void RemoveAll()
	{
		CContour *pCnt = m_pContourHead;
		while ( pCnt != NULL )
		{
			CContour *pHead = pCnt->m_pNext;
			pCnt->m_pNext = NULL;
			pCnt->m_pPrev = NULL;
			delete pCnt;
			pCnt = pHead;
		}
		m_nSize = 0;
	}
	void AddHead( CContour *pCon )
	{
		if( m_pContourHead == NULL && m_pContourTail == NULL )
		{
			m_pContourHead = pCon;
			m_pContourTail = pCon;
			pCon->m_pNext = NULL;
			pCon->m_pPrev = NULL;
		}
		else
		{
			CContour *pOldHead = m_pContourHead;
			m_pContourHead = pCon;
			pOldHead->m_pPrev = m_pContourHead;
			m_pContourHead->m_pNext = pOldHead;
			m_pContourHead->m_pPrev = NULL;
		}
		m_nSize++;
	}
	void AddTail( CContour *pCon )
	{
		if( m_pContourHead == NULL && m_pContourTail == NULL )
		{
			m_pContourHead = pCon;
			m_pContourTail = pCon;
			pCon->m_pNext = NULL;
			pCon->m_pPrev = NULL;
		}
		else
		{
			CContour *pOldTail = m_pContourTail;
			m_pContourTail = pCon;
			pOldTail->m_pNext = m_pContourTail;
			m_pContourTail->m_pPrev = pOldTail;
			m_pContourTail->m_pNext = NULL;
		}
		m_nSize++;
	}
	int GetSize()
	{
		return m_nSize;
	}
	void Remove( CContour* pC )
	{
		if( pC == m_pContourHead )
		{
			m_pContourHead = m_pContourHead->m_pNext;
			m_pContourHead->m_pPrev = NULL;
		}
		else if( pC == m_pContourTail )
		{
			m_pContourTail = m_pContourTail->m_pPrev;
			m_pContourTail->m_pNext = NULL;
		}
		else
		{
			CContour* p1 = pC->m_pPrev;
			CContour* p2 = pC->m_pNext;
			p1->m_pNext = p2;
			p2->m_pPrev = p1;
		}
		delete pC;
	}
};


#define HUGE_PENALTY 10e10

typedef CContour* PCContour;

class CFVector
{
public:
	int m_nDim;// dimention
	float *m_pData;// pointer to the data
	CFVector()
	{
		m_nDim = 0;
		m_pData = NULL;
	}
	CFVector( int nDim )
	{
		m_nDim = nDim;
		m_pData = new float[m_nDim];
		if( !m_pData )
		{
//			::MessageBox( NULL, "Memory Located error", "Error", MB_OK );
		}
	}
	CFVector( CFVector & v )
	{
		CFVector( v.m_nDim );
		memcpy( m_pData, v.m_pData, sizeof(float) * m_nDim );
	}
	void Create( int nDim )
	{
		if( m_nDim != nDim )
		{
			ClearData();
			m_nDim = nDim;
			m_pData = new float[m_nDim];
			if( !m_pData )
			{
//				::MessageBox( NULL, "Memory Located error", "Erroe", MB_OK );
			}
		}
	}
	~CFVector()
	{
		ClearData();
	}
	void ClearData()
	{
		if( m_pData != NULL )
		{
			delete [] m_pData;
			m_pData = NULL;
			m_nDim = 0;
		}
	}
	CFVector & operator = ( CFVector & v )
	{
		ClearData();
		CFVector( v.m_nDim );
		memcpy( m_pData, v.m_pData, sizeof(float) * m_nDim );
		return *this;
	}
	float GetLength()
	{
		if( m_pData == NULL )
			return 0;
		float fLength = 0;
		for( int i = 0; i < m_nDim; i++ )
		{
			fLength += m_pData[i] * m_pData[i];
		}
		fLength = (float)sqrt( fLength );
		return fLength;
	}
	float GetAngle()
	{
		if( m_pData == NULL || m_nDim != 2 )
			return 400;
		float fAngle = (float)atan2( m_pData[1], m_pData[0] );
		fAngle = (float)( fAngle * 180.0 / PI );
		return fAngle;
	}
};//class CFVector


typedef SimpleMatrix<PCContour> SPCMatrix;


#endif//_STRUCTURES2_H_
